// Created by WXX on 2021/10/24 11:13
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：24 ms, 在所有 C++ 提交中击败了70.79%的用户
 * 内存消耗：22.6 MB, 在所有 C++ 提交中击败了44.56%的用户
 */
class Solution {
public:

    int n;  // 商品数量
    vector<unordered_map<int, int>> f;  // 状态转移数组
    vector<int> price;  // 每个物品的价格
    vector<vector<int>> special;  // 大礼包

    int dp(int x, int y) {
        if (f[x].count(y)) return f[x][y];

        if (!x) {  // 大礼包编号从1开始，0表示选择单个物品
            f[x][y] = 0;
            for (int i = 0; i < n; i++) {
                int c = y >> i * 4 & 15;  // y表示的状态中第i件商品需要的数目
                f[x][y] += c * price[i];
            }
            return f[x][y];
        }

        f[x][y] = dp(x - 1, y);
        int state = 0;
        auto s = special[x - 1];  // 第x件大礼包对应下标是x-1
        for (int i = n - 1; i >= 0; i--) {
            int c = y >> i * 4 & 15;  // y表示的状态中第i件商品需要的数目
            if (c < s[i]) {  // 说明不能使用这个大礼包
                state = -1;
                break;
            }
            state = state * 16 + c - s[i];
        }
        if (state != -1)
            f[x][y] = min(f[x][y], dp(x, state) + s.back());
        return f[x][y];
    }

    // f[i, J] = min(f[i - 1, J], f[i][J - Vi] + Wi)
    // J 是 [j0, j1, j2, j3, j4, j5] 的简写，代码中使用16进制表示
    // 下标对应的关系 j0: 0000~1111, j1: 0000 0000~1111 0000, ...
    int shoppingOffers(vector<int>& _price, vector<vector<int>>& _special, vector<int>& needs) {

        price = _price, special = _special;
        n = price.size();
        f = vector<unordered_map<int, int>>(special.size() + 1, unordered_map<int, int>());
        // 将需要购买的物品数量转化为8进制
        int state = 0;
        for (int i = needs.size() - 1; i >= 0; i--)
            state = state * 16 + needs[i];

        return dp(special.size(), state);
    }
};

int main() {

    vector<int> price = {2, 5};
    vector<vector<int>> special = {
            {3, 0, 5},
            {1, 2, 10},
    };
    vector<int> needs = {3, 2};
    cout << Solution().shoppingOffers(price, special, needs) << endl;  // 14

    return 0;
}
